import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;


    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};

class Solution {
    int[][] arr;
    public Node construct(int[][] grid) {
        arr=grid;
        return dfs(0,0,grid.length);
    }
    public Node dfs(int x,int y,int len){
        if(len==1){
            return new Node(arr[x][y]==1,true);
        }
        int mid=len/2;
        Node left=dfs(x,y,mid);
        Node right=dfs(x,y+mid,mid);
        Node lowerL=dfs(x+mid,y,mid);
        Node lowerR=dfs(x+mid,y+mid,mid);
        if(left.isLeaf&&right.isLeaf&&lowerL.isLeaf&&lowerR.isLeaf&&left.val==right.val&&left.val==lowerL.val&&lowerL.val==lowerR.val){
            return new Node(left.val,true);
        }else{
            return new Node(false,false,left,right,lowerL,lowerR);
        }
    }
}
public class project {
    public boolean isBipartite(int[][] graph) {
        int[] arr=new int[graph.length];
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<arr.length;i++){
            if(arr[i]!=0){
                continue;
            }
            arr[i]=1;
            queue.add(i);
            while (!queue.isEmpty()){
                int index=queue.poll();
                for(int value:graph[index]){
                    if(arr[index]==arr[value]){
                        return false;
                    }
                    if(arr[value]==0){
                        arr[value]=-arr[index];
                        queue.offer(value);
                    }
                }
            }
        }
        return true;
    }



















    public boolean isBipartite1(int[][] graph) {
        int[] arr=new int[graph.length];
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<arr.length;i++){
            if(arr[i]!=0){
                continue;
            }
            queue.add(i);
            arr[i]=1;
            while (!queue.isEmpty()){
                int value=queue.poll();
                for(int x:graph[value]){
                    if(arr[x]==arr[value]){
                        return false;
                    }
                    if(arr[x]==0){
                        arr[x]=-arr[value];
                        queue.offer(x);
                    }
                }
            }
        }
        return true;
    }



















    public double[] dicesProbability(int n) {
        double[] dp=new double[6];
        Arrays.fill(dp,1.0/6.0);
        for(int i=2;i<=n;i++){
            double[] tmp=new double[5*i+1];
            for(int j=0;j<dp.length;j++){
                for(int k=0;k<6;k++){
                    tmp[j+k]+=dp[j]/6.0;
                }
            }
            dp=tmp;
        }
        return dp;
    }
}
